#include "TreeOperator.h"
bool isSymmetric(TreeNode *root1, TreeNode *root2) {
    if (!root1 && !root2) {
        return true;
    } else if (!root1 && root2) {
        return false;
    } else if (root1 && !root2) {
        return false;
    } else {
        if (root1->val != root2->val)
            return false;
        else
            return isSymmetric(root1->left, root2->right) &&
                   isSymmetric(root1->right,
                               root2->left); // 节点都不为空并且左右节点值相同
    }
}
bool isSymmetric(TreeNode *root) {
    if (!root)
        return true;
    else {
        return isSymmetric(root, root); // 根节点左右相同
    }
}
bool isSameTree(TreeNode *root1, TreeNode *root2) {
    if (!root1 && !root2)
        return true;
    else if (!root1 && root2)
        return false;
    else if (root1 && !root2)
        return false;
    else {
        if (root1->val != root2->val)
            return false;
        else {
            return isSameTree(root1->left, root2->left) &&
                   isSameTree(root1->right, root2->right);
        }
    }
}
// root1 是否包含 root2
bool isContainSubTree(TreeNode *root1, TreeNode *root2) {
    if (!root1 && !root2)
        return false; // 空树不包含任何子结构
    else if (root1 && !root2)
        return true;
    else if (!root1 && root2)
        return false;
    else {
        if (isSameTree(root1, root2)) {
            return true;
        } else {
            return isContainSubTree(root1->left, root2) ||
                   isContainSubTree(root1->right, root2);
        };
    }
}

TreeNode *mirrorTreeRecursive(TreeNode *root) {
    if (!root)
        return root;
    else {
        TreeNode *tmp = root->right;
        root->right = mirrorTree(root->left);
        root->left = mirrorTree(tmp);
        return root;
    }
}

// 使用栈对非叶子节点左右交换
TreeNode *mirrorTree(TreeNode *root) {
    if (!root)
        return root;
    else {
        std::stack<TreeNode *> s;
        s.push(root);
        while (!s.empty()) {
            TreeNode *current = s.top();
            s.pop();
            TreeNode *temp = current->left;
            current->left = current->right;
            current->right = temp;
            if (current->left)
                s.push(current->left);
            if (current->right)
                s.push(current->right);
        }
        return root;
    }
}

bool isValidBST(TreeNode *root, long min, long max) {
    if (!root)
        return true;                        // 根节点为空
    if (root->val > min && root->val < max) // 判断的入口
        return isValidBST(root->left, min, root->val) &&
               isValidBST(root->right, root->val, max);
    else
        return false;
}

bool isValidBST(TreeNode *root) {
    return isValidBST(root, std::numeric_limits<long>::min(),
                      std::numeric_limits<long>::max());
}
// minDepth with recursive
int minDepth(TreeNode *root) {
    if (!root)
        return 0;
    else {
        if (!root->left && root->right)
            return minDepth(root->right) + 1;
        if (root->left && !root->right)
            return minDepth(root->left) + 1;
        return std::min(minDepth(root->left), minDepth(root->right)) + 1;
    }
}
// BFS find first node
int minDepthWithBFS(TreeNode *root) {
    if (!root)
        return 0;
    else {
        std::queue<std::pair<TreeNode *, int>> node_and_level;
        node_and_level.emplace(root, 1);
        int n = 1;
        while (!node_and_level.empty()) {
            TreeNode *node = node_and_level.front().first;
            int level = node_and_level.front().second;
            node_and_level.pop();
            if (node->left)
                node_and_level.emplace(node->left, level + 1);
            if (node->right)
                node_and_level.emplace(node->right, level + 1);
            if (!node->left && !node->right) { // isLeaf
                n = level;
                break;
            }
        }
        return n;
    }
}

int maxDepth(TreeNode *root) {
    if (!root)
        return 0;
    else {
        if (!root->left && root->right)
            return minDepth(root->right) + 1;
        if (root->left && !root->right)
            return minDepth(root->left) + 1;
        return std::max(minDepth(root->left), minDepth(root->right)) + 1;
    }
}

std::vector<TreeNode *> getPath(TreeNode *root, TreeNode *target) {
    // target 不可能为空找到target将路径存储起来
    std::vector<TreeNode *> result;
    TreeNode *node = root;
    while (node) {
        result.push_back(node);
        if (node->val < target->val)
            node = node->right;
        else if (node->val > target->val)
            node = node->left;
        else
            break;
    }
    return result;
}

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    std::vector<TreeNode *> p_path = getPath(root, p);
    std::vector<TreeNode *> q_path = getPath(root, q);
    TreeNode *current = root;
    int min_loop = std::min(q_path.size(), p_path.size());
    int index = 0;
    for (int i = 0; i < min_loop; i++) {
        if (q_path[i] == p_path[i]) {
            index = i;
            continue;
        } else {
            break;
        }
    }
    return p_path[index];
}

bool hasPathSum(TreeNode *root, int sum) {
    if (!root)
        return false;
    else {
        // 到达叶子节点
        if (!root->left && !root->right)
            return sum == root->val;
        else {
            return hasPathSum(root->left, sum - root->val) ||
                   hasPathSum(root->right, sum - root->val);
        }
    }
}

int maxDepth(Node *root) {
    if (!root)
        return 0;
    else {
        std::vector<Node *> children = root->children;
        int max = 1;
        for (auto node : children) {
            max = std::max(maxDepth(node) + 1, max);
        }
        return max;
    }
}

std::vector<std::vector<int>> levelOrderRecord(TreeNode *root) {
    std::vector<vector<int>> result;
    if (!root)
        return result;
    else {
        std::queue<TreeNode *> node_queue;
        std::vector<int> level_nodes;
        int nodes = 0;
        node_queue.push(root);
        while (!node_queue.empty()) {
            nodes = node_queue.size();
            for (int n = 0; n < nodes; n++) {
                TreeNode *pCurrent = node_queue.front();
                level_nodes.push_back(pCurrent->val);
                if (pCurrent->left)
                    node_queue.push(pCurrent->left);
                if (pCurrent->right)
                    node_queue.push(pCurrent->right);
                node_queue.pop();
            }
            result.emplace_back(level_nodes);
            level_nodes.clear();
        }
        return result;
    }
}
TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) {
    if (!t1 && t2)
        return t2;
    else if (t1 && !t2)
        return t1;
    else if (!t2 && !t1)
        return nullptr;
    else {
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
}

void binaryTreePaths(TreeNode *root, std::vector<std::string> &cache,
                     std::string msg) {
    if (!root)
        return;
    else {
        msg += std::to_string(root->val);
        if (!root->left && !root->right) {
            cache.push_back(msg);
        } else {
            msg += "->";
            if (root->left) {
                binaryTreePaths(root->left, cache, msg);
            }
            if (root->right) {

                binaryTreePaths(root->right, cache, msg);
            }
        }
    }
}

std::vector<std::string> binaryTreePathsDFS(TreeNode *root) {
    std::vector<std::string> result;
    std::string msg;
    binaryTreePaths(root, result, msg);
    return result;
}

std::vector<std::string> binaryTreePaths(TreeNode *root) {
    std::vector<std::string> result;
    if (!root) {
        return result;
    } else {
        std::stack<TreeNode *> dfs_stack;
        std::stack<std::string> path_str;
        dfs_stack.push(root);
        std::string msg;
        path_str.push(msg);
        while (!dfs_stack.empty()) {
            TreeNode *pCurrent = dfs_stack.top();
            dfs_stack.pop();
            msg = path_str.top();
            path_str.pop();
            msg += std::to_string(pCurrent->val);
            if (!pCurrent->left && !pCurrent->right) {
                result.push_back(msg);
            } else {
                msg += "->";
                if (pCurrent->right) {
                    dfs_stack.push(pCurrent->right);
                    path_str.push(msg);
                }

                if (pCurrent->left) {

                    dfs_stack.push(pCurrent->left);
                    path_str.push(msg);
                }
            }
        }
    }
    return result;
}

// int sumNumbers(TreeNode *root) {
//     if (!root)
//         return 0;
//     std::stack<int> nodes;
//     std::stack<int> values;
//     nodes.push(root);
//     value.push(root->val);
//     int path_sum = 0;
//     int current_sum = 0;
//     int node_value = 0;
//     while (!nodes.empty()) {
//         TreeNode *pCurrent = nodes.top();
//         nodes.pop();
//         node_value = values.top();
//         values.pop();
//         if (pCurrent->left) {
//             nodes.push(pCurrent->left);
//             values.push(pCurrent->left->val);
//         }
//         if (pCurrent->right) {
//             nodes.push(pCurrent->right);
//             values.push(pCurrent->right->val);
//         }
//         if (!pCurrent->right && !pCurrent->left) {
//             path_sum += current_sum;
//             values.pop();
//         } else {
//             node_value = 10*
//             current_sum = 10 * node_value + current_sum;
//         }
//     }
// }

int binaryMaxTreePathsSum(TreeNode *root) {
    std::vector<int> result;
    int max_value = 0;
    if (!root) {
        return 0;
    } else {
        std::stack<TreeNode *> dfs_stack;
        std::vector<int> path_sum;
        dfs_stack.push(root);
        int current_sum = 0;
        int value = 0;
        path_sum.push_back(root->val);
        while (!dfs_stack.empty()) {
            TreeNode *pCurrent = dfs_stack.top();
            dfs_stack.pop();

            value = *path_sum.begin();
            path_sum.pop_back();
            current_sum += value;
            if (!pCurrent->left && !pCurrent->right) {
                max_value = std::max(current_sum, max_value);
                current_sum -= value;
            } else {
                if (pCurrent->right) {
                    dfs_stack.push(pCurrent->right);
                    path_sum.push_back(pCurrent->right->val);
                }
                if (pCurrent->left) {
                    dfs_stack.push(pCurrent->left);
                    path_sum.push_back(pCurrent->left->val);
                }
            }
        }
    }
    return max_value;
}

void travelTree(TreeNode *root, std::vector<int> &cache) {
    if (!root)
        return;
    else {
        cache.push_back(root->val);
        travelTree(root->left, cache);
        travelTree(root->right, cache);
    }
}
std::vector<int> travelTree(TreeNode *root) {
    std::vector<int> cache;
    travelTree(root, cache);
    return cache;
}
void travelInNode(TreeNode *root, std::queue<TreeNode *> &cache) {
    if (!root)
        return;
    else {
        cache.push(root);
        travelInNode(root->left, cache);
        travelInNode(root->right, cache);
    }
}
void flatten(TreeNode *root) {
    std::queue<TreeNode *> cache;
    travelInNode(root, cache);
    if (cache.empty())
        return;
    else {
        TreeNode *pCurrent = cache.front();
        cache.pop();
        while (!cache.empty()) {
            TreeNode *pTemp = cache.front();
            cache.pop();
            pCurrent->right = pTemp;
            pCurrent->left = nullptr;
            pCurrent = pTemp;
        }
        root = pCurrent;
    }
}
void inorderTravel(TreeNode *root, std::vector<int> &cache) {
    if (!root)
        return;
    else {
        inorderTravel(root->right, cache);
        cache.push_back(root->val);
        inorderTravel(root->left, cache);
    }
}

vector<int> inorderTravel(TreeNode *root) {
    std::vector<int> cache;
    inorderTravel(root, cache);
    return cache;
}

int kthLargest(TreeNode *root, int k) {
    if (!root)
        return 0;
    else {
        std::vector<int> s = inorderTravel(root);
        return s[k - 1];
    }
}

int widthOfBinaryTree(TreeNode *root) {
    if (!root)
        return 0;
    else {
        std::queue<std::pair<long long unsigned, TreeNode *>> q;
        q.emplace(0, root);
        TreeNode *node;
        unsigned long long index = 0;
        unsigned long long max_depth = 1;
        int i;
        unsigned long long first;
        while (!q.empty()) {
            int n = q.size();
            i = 0;
            while (i < n) {
                std::tie(index, node) = q.front();
                if (i == 0)
                    first = index;
                q.pop();
                if (node->left) {
                    q.emplace(index * 2 + 1, node->left);
                }
                if (node->right) {
                    q.emplace(index * 2 + 2, node->right);
                }
                i++;
            }
            max_depth = std::max(max_depth, index - first + 1);
        }
        return max_depth;
    }
}

int dfsMaxPathSum(TreeNode *root, int path_sum) {
    if (!root) {
        return path_sum;
    } else {
        path_sum += root->val;
        int sum = std::max(dfsMaxPathSum(root->left, path_sum),
                           dfsMaxPathSum(root->right, path_sum));
        return sum;
    }
}

int dfsMaxPathSum(TreeNode *root) { return dfsMaxPathSum(root, 0); }
int maxPathSum(TreeNode *root, int &val) {
    if (!root)
        return 0;
    else {
        int left_sum = maxPathSum(root->left, val);
        int right_sum = maxPathSum(root->right, val);
        int includeRootSum =
            root->val + std::max(0, left_sum) + std::max(0, right_sum);
        int ret = root->val + std::max(0, std::max(left_sum, right_sum));
        val = std::max(val, includeRootSum);
        return ret;
    }
}
int maxPathSum(TreeNode *root) {
    int max_value = std::numeric_limits<int>::min();
    maxPathSum(root, max_value);
    return max_value;
}

TreeNode *buildTree(const vector<int> &preorder, const vector<int> &inorder,
                    int pleft, int pright, int ileft, int iright,
                    std::unordered_map<int, int> &index) {
    if (pleft > pright) {
        return nullptr;
    }

    int proot = pleft;
    // 在中序遍历中定位根节点
    int iroot = index[preorder[proot]];

    // 先把根节点建立出来
    TreeNode *root = new TreeNode(preorder[proot]);
    // 得到左子树中的节点数目
    int lsubtree_size = iroot - ileft;
    root->left = buildTree(preorder, inorder, pleft + 1, pleft + lsubtree_size,
                           ileft, iroot - 1, index);
    root->right = buildTree(preorder, inorder, pleft + lsubtree_size + 1,
                            pright, iroot + 1, iright, index);
    return root;
}

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
    int n = preorder.size();
    // node value --> index
    std::unordered_map<int, int> index;
    for (int i = 0; i < n; ++i) {
        index[inorder[i]] = i;
    }
    return buildTree(preorder, inorder, 0, n - 1, 0, n - 1, index);
}

int sumOfTree(TreeNode *root) {
    if (!root)
        return 0;
    else {
        root->val += sumOfTree(root->right);
        if (root->left)
            root->left->val += root->val;
        return root->val;
    }
}
TreeNode *convertBST(TreeNode *root) {
    if (!root)
        return root;
    else {
        int sum = sumOfTree(root);
        return root;
    }
}

// bool isCompleteTree(TreeNode *root) {
//     if (!root)
//         return false;
//     else {
//         std::queue<std::pair<int, TreeNode *>> level_node;
//         level_node.push({0, root});
//         int level;
//         TreeNode *pCurrent;
//         int level_nums = 1;
//         bool flag = true;
//         while (!level_node.empty()) {
//             level_nums = level_node.size();
//             std::tie(level, pCurrent) = level_node.front();
//             level_node.pop();
//             if (level_nums != (level << level)) {
//                 flag = false;
//                 break;
//             }
//             if (pCurrent->left)
//                 level_node.push({level + 1, pCurrent->left});
//             if (pCurrent->right)
//                 level_node.push({level + 1, pCurrent->right});
//         }
//     }
// }
//  std::vector<std::vector<int>> zigzagLevelOrder(TreeNode *root) {}
